package com.example.maze.solver;

import com.example.maze.model.Cell;
import com.example.maze.model.Coordinate;
import com.example.maze.model.Maze;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.*;

/**
 * A*寻路算法实现
 * 使用优先队列和启发式函数进行最优路径搜索
 * 
 * 算法特点：
 * - 结合了BFS的最优性和DFS的效率
 * - 使用f(n) = g(n) + h(n)评估函数
 * - g(n): 从起点到当前节点的实际代价
 * - h(n): 从当前节点到终点的启发式估计
 * - 保证找到最短路径（在启发式函数可接受的情况下）
 * 
 * @author maze-demo
 */
public class AStarSolver implements MazeSolver {
    private static final Logger logger = LoggerFactory.getLogger(AStarSolver.class);

    @Override
    public SolverResult solve(Maze maze) {
        logger.info("开始使用A*算法寻路");
        
        if (!maze.isValid()) {
            throw new IllegalArgumentException("迷宫无效：缺少起点或终点");
        }

        long startTime = System.currentTimeMillis();
        
        // 重置迷宫状态
        maze.reset();
        
        // 初始化
        Cell startCell = maze.getStartCell();
        Cell endCell = maze.getEndCell();
        Coordinate endCoord = endCell.getCoordinate();
        
        // 使用优先队列，按f值排序
        PriorityQueue<Cell> openSet = new PriorityQueue<>(Comparator.comparingInt(Cell::getFCost));
        Set<Coordinate> openSetCoords = new HashSet<>();
        Set<Coordinate> closedSet = new HashSet<>();
        Map<Cell, Cell> parentMap = new HashMap<>();
        
        // 初始化起点
        startCell.setGCost(0);
        startCell.setHCost(calculateHeuristic(startCell.getCoordinate(), endCoord));
        openSet.offer(startCell);
        openSetCoords.add(startCell.getCoordinate());
        
        int visitedCount = 0;
        
        logger.debug("A*开始: 起点={}, 终点={}, 初始h值={}", 
            startCell.getCoordinate(), endCoord, startCell.getHCost());
        
        // A*主循环
        boolean found = false;
        while (!openSet.isEmpty() && !found) {
            Cell current = openSet.poll();
            Coordinate currentCoord = current.getCoordinate();
            openSetCoords.remove(currentCoord);
            closedSet.add(currentCoord);
            visitedCount++;
            
            // 标记当前单元格为已访问（用于可视化）
            if (current.getType() == Cell.Type.PATH) {
                current.setType(Cell.Type.VISITED);
            }
            
            logger.trace("A*访问: {}, g={}, h={}, f={}", 
                currentCoord, current.getGCost(), current.getHCost(), current.getFCost());
            
            // 检查是否到达终点
            if (current.equals(endCell)) {
                found = true;
                logger.debug("A*找到终点: {}", currentCoord);
                break;
            }
            
            // 检查所有邻居
            List<Cell> neighbors = maze.getPassableNeighbors(current);
            
            for (Cell neighbor : neighbors) {
                Coordinate neighborCoord = neighbor.getCoordinate();
                
                // 跳过已经在封闭集合中的节点
                if (closedSet.contains(neighborCoord)) {
                    continue;
                }
                
                // 计算从起点到邻居的暂定g值
                int tentativeGCost = current.getGCost() + 1; // 移动代价为1
                
                // 如果这个邻居不在开放集合中，或者我们找到了更好的路径
                if (!openSetCoords.contains(neighborCoord) || tentativeGCost < neighbor.getGCost()) {
                    // 更新邻居的代价和父节点
                    neighbor.setGCost(tentativeGCost);
                    neighbor.setHCost(calculateHeuristic(neighborCoord, endCoord));
                    parentMap.put(neighbor, current);
                    
                    logger.trace("A*更新邻居: {}, g={}, h={}, f={}", 
                        neighborCoord, neighbor.getGCost(), neighbor.getHCost(), neighbor.getFCost());
                    
                    // 如果邻居不在开放集合中，添加它
                    if (!openSetCoords.contains(neighborCoord)) {
                        openSet.offer(neighbor);
                        openSetCoords.add(neighborCoord);
                        logger.trace("A*加入开放集合: {}", neighborCoord);
                    }
                }
            }
        }
        
        long endTime = System.currentTimeMillis();
        long timeMillis = endTime - startTime;
        
        if (found) {
            // 重建路径
            List<Coordinate> path = reconstructPath(parentMap, startCell, endCell);
            // 不再自动标记路径，由主程序控制
            // markSolutionPath(maze, path);
            
            logger.info("A*寻路成功: 路径长度={}, 访问节点={}, 耗时={}ms", 
                path.size(), visitedCount, timeMillis);
            
            return new SolverResult("A*", path, visitedCount, timeMillis);
        } else {
            logger.info("A*寻路失败: 访问节点={}, 耗时={}ms", visitedCount, timeMillis);
            return SolverResult.notFound("A*", visitedCount, timeMillis);
        }
    }

    /**
     * 计算启发式函数值（曼哈顿距离）
     * 在网格迷宫中，曼哈顿距离是可接受的启发式函数
     */
    private int calculateHeuristic(Coordinate from, Coordinate to) {
        return from.manhattanDistance(to);
    }

    /**
     * 重建从起点到终点的路径
     */
    private List<Coordinate> reconstructPath(Map<Cell, Cell> parentMap, Cell start, Cell end) {
        List<Coordinate> path = new ArrayList<>();
        Cell current = end;
        
        // 从终点向起点回溯
        while (current != null) {
            path.add(current.getCoordinate());
            current = parentMap.get(current);
        }
        
        // 反转路径，使其从起点到终点
        Collections.reverse(path);
        
        logger.debug("A*重建路径: {} 个节点", path.size());
        return path;
    }

    /**
     * 标记解决方案路径
     */
    private void markSolutionPath(Maze maze, List<Coordinate> path) {
        for (Coordinate coord : path) {
            Cell cell = maze.getCell(coord);
            if (cell.getType() != Cell.Type.START && cell.getType() != Cell.Type.END) {
                cell.setType(Cell.Type.SOLUTION);
            }
        }
    }

    @Override
    public String getName() {
        return "A*";
    }
}